package consistenthash

import (
	"hash/crc32"
	"strconv"
)

// 一致性hash算法

type Hash func(data []byte) uint32

type Map struct {
	hash     Hash
	replicas int
	keys     []int //哈希环 
	hashMap  map[int]string
}

func New(replicas int, fn Hash) *Map {
	return &Map{
		m := &Map{
			replicas: replicas,
			hash:fn,
			hashMap: make(map[int]string),
		}
		// 默认为 crc32.ChecksumIEEE 算法
		if m.hash == nil{
			m.hash = crc32.ChecksumIEEE()
		}
		return m
	}
}

func (m *Map) Add(keys ...string){
	for _,key := range keys{
		for i :=0;i<m.replicas;i++{
			hash := int(m.hash([]byte(strconv.Itoa(i)+key)))
			m.keys=append(m.keys,hash)
			m.hashMap[hash] = key
		}
	}
	// 最后一步，环上的哈希值排序
	sort.Ints(m.keys)
}


func (m *Map) Get(key string) string{
	if len(m.keys) == 0 {
		return ""
	}
	hash := int(m.hash([]byte(key)))

	idx := sort.Search(len(m.keys),func(i int) bool {
		return m.keys[i] >= hash
	})
	// 顺时针找到第一个匹配的虚拟节点的下标 idx，从 m.keys 中获取到对应的哈希值。
	// 如果 idx == len(m.keys)，说明应选择 m.keys[0]，
	// 因为 m.keys 是一个环状结构，所以用取余数的方式来处理这种情况。
	return m.hashMap[m.keys[idx%len(m.keys)]]
}
